约瑟夫问题(数组+队列+公式迭代+递归) |
您所在的位置：网站首页 › 迭代 循环 递归 › 约瑟夫问题(数组+队列+公式迭代+递归) |
|
约瑟夫问题(数组+队列+公式迭代+递归)
约瑟夫环问题起源于一个犹太故事： 罗马人攻占了桥塔帕特，41个人藏在一个山洞中躲过了这场浩劫。这41个人中，包括历史学家Josephus（约瑟夫）和他的一个朋友。剩余的39个人为了表示不向罗马人屈服，决定集体自杀。大家制定了一个自杀方案，所有这41个人围成一个圆圈，由第一个人开始顺时针报数，每报数为3的人就立刻自杀，然后再由下一个人重新开始报数，仍然是每报数为3的人就立刻自杀……，直到所有的人都自杀身亡为止。约瑟夫和他的朋友并不想自杀，于是约瑟夫想到了一个计策，他们两个同样参与到自杀方案中，但是最后却躲过了自杀。 简化一下问题(不这么血腥的例题): 设有n个人围坐一圈，编号为1到n，现从编号为1的人开始报数，数到m的人出列，接着从出列的下一个编号（人）开始重新报数，数到m的人出列，如此下去，直到只剩下最后一个人，并输出其编号。 例如输入 4 5输出结果 2 用数组的思路很简单（这也是刚开始接触这道题我的做法）基本思路(容易理解):一开始，将全部数字存入数组中并全部初始化为0，定义一个变量c表示当前数到的人的编号，再定义一个变量k表示从1开始数到m的人的个数，再再定义一个变量s表示出圈的人的个数。 代码如下: #include using namespace std; int main() { int n,m;//n表示多少个人参与游戏，m表示数到多少个人出圈 cin>>n>>m; int arr[1000]= {0}; //0表示人还在圈中 int k=0;//报数数到几 int c=0;//当前人的编号 int s=0;//出圈的人数和 while(s!=n) { c++; if(c>n)c=1;//大于总人数时，重新开始报数 if(arr[c]==0) { k++; if(m==k) { arr[c]=1;//标记后下次不报数 s++; //cout |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |